Cleaning tasks of the cleaning service company often have the characteristics such as different levels, different durations and different cycles, and lack a general cleaning scheduling problem model. At present, the solving of cleaning scheduling problem is mainly relies on manual scheduling scheme, causing the problems such as time-consuming, labor-consuming and unstable scheduling quality. Therefore, a mathematical model of cleaning scheduling problem with constraints, which is a NP-hard problem, was proposed, then Simulated Annealing algorithm (SA), Bee Colony Optimization algorithm (BCO), Ant Colony Optimization algorithm (ACO), and Particle Swarm Optimization algorithm (PSO) were utilized to solve the proposed constrained cleaning scheduling problem. Finally, an empirical analysis was carried out by using the real scheduling state of a cleaning service company. Experimental results show that compared with the manual scheduling scheme, the heuristic intelligent optimization algorithms have obvious advantages in solving the constrained cleaning scheduling problem, and the manpower demand of the obtained cleaning schedule reduced significantly. Specifically, these algorithms can make the cleaning manpower in one year scheduling cycle be saved by 218.62 hours to 513.30 hours compared to manual scheduling scheme. It can be seen that the mathematical models based on heuristic intelligent optimization algorithms are feasible and efficient in solving cleaning scheduling problem with constraints, and provide making-decision supports for the scientific management of the cleaning service company.